package com.company;

/**
 * @author zhf
 * @date 2021/10/26
 */

import java.util.Arrays;

/**
 * 寻找排序数组中查找元素的第一个和最后一个位置
 *
 * 使用二分法
 */
public class SearchRange {
    public static void main(String[] args) {
        SearchRange searchRange = new SearchRange();
        int[] nums = new int[]{5,7,7,8,8,10};
        int target = 7;
        int[] ans = searchRange.searchRange(nums,target);
        System.out.println(Arrays.toString(ans));
    }

    public int[] searchRange(int[] nums, int target) {
        int[] ans ;
        int first = binarySearch(nums,target,true);
        int last = binarySearch(nums,target,false) - 1;
        if (first <= last && last < nums.length && nums[first] == target && nums[last] == target){
            ans = new int[]{first,last};
        }else {
            ans = new int[]{-1,-1};
        }
        return ans;
    }

    /*
    二分法
     */

    /***
     *
     * @param nums  传入的数组；
     * @param target  目标值；
     * @param n  判断是否为寻找最后一个目标值；
     * @return  返回找到目标值的下标；
     */


    public int binarySearch(int[] nums,int target,boolean n){
        int left = 0, right = nums.length - 1;
        int ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (n && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            }else {
                left = mid + 1;
            }
        }
        return ans;
    }
}
